\documentclass[11pt]{ctexart}
\usepackage{graphicx}
\usepackage{ctex}
\usepackage[a4paper,left=1.25in,right=1.25in,top=1in,bottom=1in]{geometry}

\title{作业报告}
\author{刘小川  \\ 学号 3210105317}

\begin{document}
\maketitle
\section{设计思路}
\begin{enumerate}
\item
首先在教材上AvlTree.h的基础上，我设计了findele函数。这个函数的设计思路同AvlTree类的其他函数一样
采用了递归的想法，这个函数的作用是找到在x,y之间的所有元素，并将其输出。\par
{
\centering\includegraphics[width=0.9\textwidth]{function1.png}
\par
\centering\includegraphics[width=0.9\textwidth]{function2.png}

}
\item
其次在设计main.cpp函数时，我采用了有序数组的插入，然后在使用之前设计的findele函数，将在x，y之间的数组元素打出，
并计时。
\item
这个测试的目的是验证其平均效率为O（K+log N）所以我计划分别用固定的K和N来测试其时间的变化，来求出
其效率，其中K为输出的元素个数，因此就改变x,y之间的差值即可。\par
在开始设计时我有想过用打乱的数组作为插入元素，但是比起单调连续的数组，其x,y之间的元素个数不确定，也就
无法确定K，因此我改用了单调连续数组作为平衡树的插入元素。

\end{enumerate}

\section{理论分析}
在我设计的算法中，findele函数所用的时间分两部分，其中打印部分，时间就为打印出的元素个数K，而由于这是一个平衡树，
在迭代过程中，最大迭代次数为logN,这里的平均时间复杂度应该为O（logN）。

\section{数值结果分析}

下面我们通过不同的数值输入，来对数值结果进行分析。\par
在测试过程中，输入了三个数据，分别为num，x，y，这三个数值num代表树的总节点个数，
x和y分别是要找的元素的最大和最小范围。
\begin{itemize}
\item
首先验证O（K）的正确性，我们固定num=1000,分别将K以梯度20上升，并绘制图表。
{
\centering\includegraphics[width=0.9\textwidth]{图片1.png}

}\par
从折线图中我们可以看出，其复杂度大致随K呈线性变化。
\item
接下来我们验证的是复杂度根据N呈logN变化。我们固定K=100,然后将num逐步提升，
这里让x=0，目的是可以让二叉树搜索到最深深度，以便达成logN的搜索次数，下图是算法的时间折线图。
{
\centering\includegraphics[width=0.9\textwidth]{图片2.png}

}\par
这里我们通过变化率的变化，这个图像中，消耗时间的变化率随着N增大变小，并且整体图像呈现出logN函数的形状。

\item
在测试过程中，测试一我将num和x固定后，对y进行重定向输入，运行了25次，得到了上面的图像。
测试二则是将x和y的固定后，对num进行重定向输入，输入了25次，得到了撒谎给你免得图像


\end{itemize}

\end{document}
